//
//  RepeatedSubstringPattern.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/8/24.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  459. 重复的子字符串

import UIKit

/*
 459. 重复的子字符串

 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

 示例 1:

 输入: "abab"

 输出: True

 解释: 可由子字符串 "ab" 重复两次构成。
 示例 2:

 输入: "aba"

 输出: False
 示例 3:

 输入: "abcabcabcabc"

 输出: True

 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
 */

class RepeatedSubstringPattern: NSObject {
    
    /*
     对于字符串 s ，如果它可以由一个它的子串多次重复组成，设这个子串长度为n`  子串为s`
     则必定有：
        s` 是 s 的前缀
        n` 是 s.count 的倍数
        对于 s 中的 s`往后的任意一个位置的字符串，满足s[i] == s[i-n`]
            eg：abcabcabc 可以由abc重复三次组成，所以 n` = 3，从s[3]开始，s[3] - n` = s[0] = a; s[4] - n` = s[1] = b;
     
     所以我们可以枚举s`，由于这个前缀不会大于s的一半，所以枚举边界设置为s.count/2即可.
     
     */
    func repeatedSubstringPattern(_ s: String) -> Bool {
        let n = s.count
        if n == 1 {
            return false
        }
        let sArr = Array(s)
        for i in 1 ... n/2{
            if n%i == 0{    //表示n`必须是n的倍数
                var match = true
                for j in i ..< n{
                    if sArr[j] != sArr[j-i] {
                        match = false
                        break
                    }
                }
                if match == true {
                    return true
                }
            }
        }
        return false
    }
}
